Structural Pattern Recognition with Graph Edit Distance by Kaspar Riesen

Author:Kaspar Riesen
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

4.2.3 Genetic Search

The next improvement of Algorithm 2, which has been presented in [1], is based on a genetic search. Genetic algorithms (GAs) have been proposed in the context of error-tolerant graph matching in various publications (e.g., [3–5]). The basic idea of this approach is to formalize matchings as states (chromosomes) with a corresponding performance (fitness). An initial pool of these chromosomes, i.e., matchings, evolves iteratively into other generations. To this end, different genetic operations are applied to the current matchings. Though the search space is explored in a random fashion, genetic algorithms can be designed so as to favor promising chromosomes, i.e., well-fitting matchings, and further improve them by specific genetic operations.

The chromosomes in the genetic search procedure presented in [1] are assignments related to the original node assignment . In order to build an initial population P(0) containing chromosomes (assignments), N random variations of are computed first.

A single variation of is computed similarly to the approach described in the previous sections. That is, in an alternative assignment the nodes and are enforced to be assigned to other nodes than and , respectively. This is again ensured by means of an update of the cost matrix such that entry (corresponding to the edit operation ) is set to .

Yet, in contrast with the two former procedures, the node operation to be prohibited is randomly selected (rather than searching for the node operation that implies highest edge operation costs). More formally, every node edit operation is possibly prohibited with mutation probability p. Hence, it might be that zero, one, or more than one entry in the cost matrix is set to at once.

Given the updated cost matrix (with zero, one, or more -entries) an optimal node assignment is computed. This results in a new assignment possibly containing several altered node edit operations.

The whole mutation procedure as described above can be repeated times to the original assignment in order to get (possibly) different assignments . Additionally, the original assignment is added to P(0) such that the approximation found by this extension is guaranteed to be at least as accurate as the original approximation . Note that all of the approximate edit distances, that correspond to the assignments of the population P(0), are still equal to, or larger than, the exact edit distance. Hence, the fitness of every chromosome, i.e., assignment , can be rated according to its specific distance value . Formally, the lower is, the better the fitness of chromosome .

Given the initial population P(0) the following iterative procedure is carried out. A new population of assignments is built upon a subset , often referred to as parents. In order to select the parents from a given population P(t), the best approximations, i.e., the approximations in P(t) with lowest distance values, are selected first (). In the framework presented in [1], all approximations from E are added without any modifications to the next population . This ensures that the best solution found so far will not be lost during the search procedure (known as survival of the fittest).

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.